package main.java.com.amanda.suafa;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
import java.util.Scanner;

/*
 * @author amanda
 * @Description 算法3.1 顺序查找（基于无序链表）
 * S E A R C H E X A M P L E
 */

public class SequentialSearchST<Key, Value> {
    private int n;
    private Node first;
    private class Node {
        Key key;
        Value val;
        Node next;
        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.next = next;
            this.val = val;
        }
    }

    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("get() is null");
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key))
                return x.val;
        }
        return null;
    }

    public void put(Key key, Value val) {
        // 延时型删除
        if (key == null) throw new IllegalArgumentException("put() is null");
        if (val == null) {
            delete(key);
            return;
        }
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        }
        first = new Node(key, val, first);
        n++;
    }

    public void delete(Key key) {
        first = delete(first, key);
    }
    private Node delete(Node x, Key key) {
        if (x == null)
            return null;
        if (key.equals(x.key)) {
            n--;
            return x.next;
        }
        x.next = delete(x.next, key);
        return x;
    }

    public int size() {
        return n;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("contains() is null");
        return get(key) != null;
    }
    public Iterable<Key> keys() {
        Queue<Key> keys = new Queue<>();
        for (Node x = first; x != null; x = x.next)
            keys.enqueue(x.key);
        return keys;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String[] ste = str.split(" ");
        int N = ste.length;

        SequentialSearchST<String, Integer> st = new SequentialSearchST<String, Integer>();
        for (int i = 0; i < N; i++) {
            String key = ste[i];

            st.put(key, i);
            if (i == 6) {
                st.put(key, null);
            }
        }

        for (String s : st.keys())
            StdOut.println(s + " " + st.get(s));
    }
}
